package org.example.leetCode;

/**
 * @Author Qinkai
 * @Description TODO $
 * @Date $ 2021-09-27$
 * @Param $
 * @return $
 **/
public class NumDecodings {
    public static void main(String[] args) {
        String s = "*1";
        NumDecodings numDecodings = new NumDecodings();
        int i = numDecodings.numDecodings(s);
    }

    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            if ("*".equals(s)) {
                return 9;
            } else if (!"0".equals(s)) {
                return 1;
            }
        }
        if (s.charAt(0) == '0') {
            return 0;
        }

        char[] chars = s.toCharArray();
        long[] dp = new long[chars.length + 1];
        dp[0] = 1;
        dp[1] = chars[0] == '*' ? 9 : 1;
        for (int i = 2; i <= chars.length; i++) {
            char first = chars[i - 2];
            char second = chars[i - 1];

            if (second == '*') {
                dp[i] += 9 * dp[i - 1];
            } else if (second > '0') {
                dp[i] += dp[i - 1];
            }

            if (first == '*') {
                if (second == '*') {
                    dp[i] += 15 * dp[i - 2];
                } else if (second <= '6') {
                    dp[i] += 2 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (first == '1' || first == '2') {
                if (second == '*') {
                    dp[i] += first == '1' ? 9 * dp[i - 2] : 6 * dp[i - 2];
                } else if (first - '0' * 10 + second - '0' <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
            dp[i] %= 1000000007;
        }
        return (int) dp[s.length()];
    }
}
